Typical DP Contest A - コンテスト

提出

TLE

code: python

import itertools

n = int(input())

p = list(map(int, input().split()))

ans = set()

for i in itertools.product(0, 1, repeat=len(p)):

res = 0

for idx, j in enumerate(i):

if j:

res += pidx

ans.add(res)

print(len(ans))

code: python

n = int(input())

p = list(map(int, input().split()))

dp0 = 1

for i in p:

dpi = 1

# それぞれ一個ずつしか使えない

# for i in p:

# for j in range(10**5):

# if dpj and i + j < 10**5:

# dpj+i = 1

print(dp:15)

解答

code: python

n = int(input())

p = list(map(int, input().split()))

dp = 0 * 10001

dp0 = 1

# p は順番に走査して問題ない

for v in p:

for i in range(10001 - v, -1, -1): # 今回加算した分が影響しないように上から見ていく

if dpi:

dpi + v = 1

# print(dp)

# [1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0,

print(sum(dp))

テーマ

メモ